public class Test2 {
    //leetcode 115 不同的子序列
    public int numDistinct(String s, String t) {
        int MOD = 1000000000 + 7;
        //状态表示，同样是两个数组的dp问题，我们使用二维dp表，dp[i][j]表示t字符串[0,i]之间的子串和s字符串[0,j]之间的子序列中t[0,i]子串出现的次数
        //状态转移方程：
        //因为求的是s[0,j]之间的子序列中包含t[0,i]子串的个数，所以不管t[i]是否和s[j]相等都需要dp[i][j] += dp[i][j-1]
        //当t.charAt(i) == s.charAt(j)时dp[i][j] = dp[i-1][j-1]
        int m = t.length(),n = s.length();
        int[][] dp = new int[m+1][n+1];
        s = " " + s;
        t = " " + t;
        for (int i = 0; i <= n; i++) dp[0][i] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j-1];
                if (t.charAt(i) == s.charAt(j)) {
                    dp[i][j] += dp[i-1][j-1] % MOD;
                }
            }
        }
        return dp[m][n];
    }
}
